package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
题目大意
		无重复字符的最长子串
	
	难度系数：中等
	
	给定一个字符串，找其无重复字符的最长子串的长度。
	
	例如： "abcabcbb"的无重复字符的最长子串是"abc"，长度为3。 "bbbbb"的无重复字符的最长子串是"b"，长度为1
	TODO: 
 * @Date 2017-09-15 00：42
 */
public class _003_Longest_Substring_Without_Repeating_Characters {

	public int lengthOfLongestSubstring(String s) {
	    
	    int l = 0;
	    int r = 1;
	    
	    HashMap<Character,Integer> setv = new HashMap<Character, Integer>();
	    setv.put(s.charAt(l), 1);
	    
	    int longest = 1;
	    
	    while (r < s.length()) {
	        char chR = s.charAt(r);
	        char chL = s.charAt(l);
	        if (setv.containsKey(chR)) {
	            setv.remove(chL);
	            l++;
	        }else{
	            setv.put(chR, 1);
	            r++;
	            longest = Math.max(longest, (int)setv.size());
	        }
	    }
	    
	    return longest;
	}
	
    
    
	public static void main(String[] args) {
		_003_Longest_Substring_Without_Repeating_Characters obj = new _003_Longest_Substring_Without_Repeating_Characters();
		LogUtils.println("最长不重复前缀", obj.lengthOfLongestSubstring("abcabcbb"));;
	}

}
